package com.leetcode.LC_MED;

public class LC416 {
    public boolean canPartition(int[] nums) {//超出时间限制

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1) {//如果和为奇数则直接退出
            return false;
        } else {
            sum /= 2;
        }

        //动态规划
        return subset(nums, nums.length - 1, sum);
    }

    private boolean subset(int[] nums, int i, int num) {
        if (num == 0) {
            return true;
        } else if (i == 0) {
            return nums[i] == num;
        } else if (nums[i] < num) {
            return subset(nums, i - 1, num - nums[i]) || subset(nums, i - 1, num);
        } else {
            return subset(nums, i - 1, num);
        }
    }

    public static void main(String[] args) {
        System.out.println(new LC416().canPartition(new int[]{1, 5, 3, 5}));
    }
}
